package com.zj;


//查找相同的最长子串  使用动态规划
public class DeleteSameWord {
    public static String findMaxWord(String word1,String word2){
        int length1=word1.length();
        int length2=word2.length();
        //重合的字符数
        int maxchar=0;
        //最大重合度的索引
        int maxIndex=0;
        //初始化数组
        int[][]dp=new int[length1+1][length2+1];
        dp[0][0]=0;
        //初始化第一行
        for (int j = 0; j < length2+1; j++) {
            dp[0][j]=0;
        }
        //初始化第一列
        for (int i = 0; i < length1+1; i++) {
            dp[i][0]=0;
        }
        //给数组赋值
        for (int i = 1; i < length1+1; i++) {
            for (int j = 1; j <length2+1 ; j++) {
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;

                    if(maxchar<dp[i][j]){
                        maxchar=dp[i][j];
                        maxIndex=i-1;
                    }
                }else{
                    dp[i][j]=0;
                }
            }
        }
        if (maxchar<=1){
            return "";
        }
        //sdt ast   maxchar=1,删除s后，dt at 编辑距离为1，但实际 sdt和ast 编辑距离为3
        return word1.substring(maxIndex-maxchar+1,maxIndex+1);
    }

}
